InterviewCrunch

Beta

The Maze

Medium

Question

Given a maze represented by a matrix, start position of a ball, and the goal position, determine if it's possible for the ball to stop at the goal position.

    Rules:
  • A cell that has "1" is a wall
  • A cell that has "0" is an empty space
  • The ball cannot stop rolling until it hits a wall
  • The ball cannot change directions until it hits a wall
  • Any cells outside the boundaries of the matrix can assumed to be walls
The Maze Example 1

Input: maze = [ [0, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0] ], start = (0, 0), goal = (3, 0)

Output: True

One of the paths the ball can move is (0, 0) -> (0, 3) -> (3, 3) -> (3, 0).

The Maze Example 2

Input: maze = [ [0, 0, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 0], ], start = (0, 0), goal = (3, 0)

Output: False

The ball would not be able to roll from the start position to goal position.

The Maze Example 3

Input: maze = [ [1, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 1, 0, 0, 1] ], start = (0, 1), goal = (4, 0)

Output: True

One of the paths the ball can move is (0, 1) -> (3, 1) -> (3, 0) -> (4, 0).

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

Is it possible for the ball to roll to the goal in this maze? If so, what path could it take? 
maze = [ 
[0, 0, 1, 1] 
[1, 0, 0, 0] 
[0, 0, 0, 0] 
[0, 0, 1, 0] 
] 
start = (0, 0) 
end = (3, 3)
True: (0, 0) -> (0, 1) -> (1, 1) -> (1, 3) -> (3, 3)
True: (0, 0) -> (0, 1) -> (3, 1) -> (3, 0) -> (2, 0) -> (2, 3) -> (3, 3)
True: (0, 0) -> (0, 1) -> (3, 1) -> (3, 3)
False

Login or signup to save your code.

Notes

PrevFlood Fill
NextWord Ladder